from cmath import inf


class MinStack:

    """
    一种更巧妙的方式，
    并不保存每次插入和弹出值时，最小值的栈，而是保存这个时机的最小值
    换言之，对于不同时机，最小值可能是重复的
    原来的方案2，缺点在于执行效率低，优点在于，可以除了最小值外，还可以查询第n小的数

    该方案保存的元组，除了值本身外，保存的第二个元素相当于一种状态。随着栈的push/pop操作进行更新,因为栈只有这两种数据操作。

    """

    def __init__(self):
        self.st = [(0, float(inf))]

    def push(self, val: int) -> None:
        self.st.append((val, min(self.st[-1][1], val)))

    def pop(self) -> None:
        self.st.pop()

    def top(self) -> int:
        return self.st[-1][0]

    def getMin(self) -> int:
        return self.st[-1][1]
